package com.yt.ds.chapter3;

/**
 * @Author: lzf
 * @Date: 2020/7/15 16:39
 * @Description: 二叉查找树，左子树比根小，右子树比根大
 */
public class BST<Key extends Comparable<Key>, Value> implements ST<Key, Value> {
    private Node root;

    private class Node {
        Node left;
        Node right;
        Key key;
        Value val;
        int n;      // 结点数 包括根节点

        private Node(Key key, Value val, int n) {
            this.key = key;
            this.val = val;
            this.n = n;
        }
    }

    @Override
    public int size() {
        return size(root);
    }

    @Override
    public void put(Key key, Value val) {
        root = put(key, val, root);
    }

    public Node put(Key key, Value val, Node node) {
        if (node == null) {
            return new Node(key, val, 1);
        }
        int com = key.compareTo(node.key);
        if (com > 0) {
            node.right = put(key, val, node.right);
        } else if (com < 0) {
            node.left = put(key, val, node.left);
        } else {
            node.val = val;
        }

        node.n = size(node.left) + size(node.right) + 1;
        return node;
    }

    @Override
    public boolean isEmpty() {
        return root == null || root.n == 0;
    }

    @Override
    public Key min() {
        return min(root).key;
    }

    private Node min(Node node) {
        if (node.left == null) {
            return node;
        }
        return min(node.left);
    }

    @Override
    public Key max() {
        return max(root).key;
    }

    private Node max(Node node) {
        if (node.right == null) {
            return node;
        }
        return max(node.right);
    }

    @Override
    public Key floor(Key key) {
        Node node = floor(root, key);
        if (node == null) {
            return null;
        }
        return node.key;
    }

    @Override
    public int rank(Key key) {
        return 0;
    }

    @Override
    public Key select(int n) {
        return null;
    }

    @Override
    public void display() {
        show(root);
    }

    private void show(Node node){
        if(node == null){
            return;
        }
        show(node.left);
        System.out.print(node.key + " ");
        show(node.right);
    }

    private Node floor(Node node, Key key) {
        if (node == null) {
            return null;
        }
        int com = key.compareTo(node.key);
        if (com < 0) {
            return floor(node.left, key);
        } else if (com == 0) {
            return node;
        } else {
            Node xNode = floor(node.right, key);
            return xNode == null ? node : xNode;
        }
    }


    @Override
    public Value get(Key key) {
        return get(key, root);
    }

    /**
     * 递归获取目标key对应的value值
     */
    public Value get(Key key, Node node) {
        if (node == null) {
            return null;
        }
        int com = key.compareTo(node.key);
        if (com > 0) {
            return get(key, node.right);
        } else if (com < 0) {
            return get(key, node.left);
        } else {
            return node.val;
        }
    }

    @Override
    public void delete(Key key) {
        root = delete(key, root);
    }

    private Node delete(Key key, Node node) {
        if(node == null){
            return null;
        }

        int com = key.compareTo(node.key);
        if(com < 0){
            node.left = delete(key,node.left);
        }else if(com > 0){
            node.right = delete(key,node.right);
        }else{
            if(node.left == null){
                return node.right;
            }
            if(node.right == null){
                return node.left;
            }
            Node temp = node;
            node = min(node.right);
            node.right = deleteMin(temp.right);
            node.left = temp.left;
        }
        node.n = size(node.left) + size(node.right) + 1;
        return node;
    }

    @Override
    public void deleteMin() {
        root = deleteMin(root);

    }

    private Node deleteMin(Node node) {
        if (node.left == null) {
            return node.right;
        }
        node.left = deleteMin(node.left);
        node.n = size(node.left) + size(node.right) + 1;
        return node;
    }

    /**
     * 获取大小
     */
    public int size(Node node) {
        return node == null ? 0 : node.n;
    }

}
